﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Clear.Algorithms
{
    public class NumAlgorithms
    {
        /// <summary>
        /// 两数之和 简单
        /// 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
        /// 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
        /// 你可以按任意顺序返回答案。
        /// 示例 1：
        /// 输入：nums = [2,7,11,15], target = 9
        /// 输出：[0,1]
        /// 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
        /// 示例 2：
        /// 
        /// 输入：nums = [3,2,4], target = 6
        /// 输出：[1,2]
        /// 示例 3：
        /// 输入：nums = [3,3], target = 6
        /// 输出：[0,1]
        /// 提示：
        /// 2 <= nums.length <= 104
        /// -109 <= nums[i] <= 109
        /// -109 <= target <= 109
        /// 只会存在一个有效答案
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static int[] TowSum(int[] nums, int target)
        {
            var l = nums.Length;
            for (int i = 0; i < l; i++)
            {
                for (int j = i + 1; j < l; j++)
                {
                    if (nums[i] + nums[j] == target)
                        return new int[] { i, j };
                }
            }
            return new int[] { 0, 0 };
        }

        /// <summary>
        /// 两数相加 中等
        /// 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
        /// 请你将两个数相加，并以相同形式返回一个表示和的链表。
        /// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
        /// 示例 1：
        /// 输入：l1 = [2,4,3], l2 = [5,6,4]
        /// 输出：[7,0,8]
        /// 解释：342 + 465 = 807.
        /// 示例 2：
        /// 输入：l1 = [0], l2 = [0]
        /// 输出：[0]
        /// 示例 3：
        /// 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
        /// 输出：[8,9,9,9,0,0,0,1]
        /// 提示：
        /// 每个链表中的节点数在范围 [1, 100] 内
        /// 0 <= Node.val <= 9
        /// 题目数据保证列表表示的数字不含前导零
        /// </summary>
        /// <param name="l1"></param>
        /// <param name="l2"></param>
        /// <returns></returns>
        public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            ListNode n = new ListNode();
            ListNode node = n;
            ListNode n1 = l1;
            ListNode n2 = l2;
            while (n1 != null || n2 != null)
            {
                int i = 0;
                int n10 = 0;
                int? v1 = n1?.val;
                int? v2 = n2?.val;

                i = (v1 ?? 0) + (v2 ?? 0) + node.val;
                if (i >= 10)
                {
                    n10 = 1;
                    node.val = i % 10;
                }
                else
                    node.val = i;

                if ((n1?.next != null || n2?.next != null))
                {
                    node.next = new ListNode(n10);
                    node = node.next;
                }
                else if (n10 == 1)
                {
                    node.next = new ListNode(n10);
                }
                n1 = n1?.next;
                n2 = n2?.next;
            }
            return n;
        }

        /// <summary>
        /// 寻找两个正序数组的中位数 困难
        /// 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
        /// 算法的时间复杂度应该为 O(log (m+n)) 。
        /// 示例 1：
        /// 输入：nums1 = [1,3], nums2 = [2]
        /// 输出：2.00000
        /// 解释：合并数组 = [1,2,3] ，中位数 2
        /// 示例 2：
        /// 输入：nums1 = [1,2], nums2 = [3,4]
        /// 输出：2.50000
        /// 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
        /// 提示：
        /// nums1.length == m
        /// nums2.length == n
        /// 0 <= m <= 1000
        /// 0 <= n <= 1000
        /// 1 <= m + n <= 2000
        /// -106 <= nums1[i], nums2[i] <= 106
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public static double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            int maxLength = nums1.Length + nums2.Length;
            int[] allInts = new int[maxLength];

            for (int i = 0; i < nums1.Length; i++)
            {
                allInts[i] = nums1[i];
            }
            for (int j = 0; j < nums2.Length; j++)
            {
                int allNow = nums1.Length + j;
                allInts[allNow] = nums2[j];
                for (int i = nums1.Length + j - 1; i >= 0; i--)
                {
                    if (allInts[i] < allInts[i + 1])
                        break;
                    else
                    {
                        int z = allInts[i + 1];
                        allInts[i + 1] = allInts[i];
                        allInts[i] = z;
                    }
                }
            }
            int m = 0;
            if (maxLength % 2 == 0)
            {
                m = maxLength / 2 + 1;
                return (allInts[m - 1] + allInts[m - 2]) / 2.0;
            }
            else
            {
                m = maxLength / 2;
                return allInts[m];
            }
        }
    }
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }
}
